package leetcode.code2039;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int networkBecomesIdle(int[][] edges, int[] patience) {
		int n = patience.length;
		List<Integer>[] nexts = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			nexts[i] = new ArrayList<>();
		}
		for (int[] edge : edges) {
			int x = edge[0], y = edge[1];
			nexts[x].add(y);
			nexts[y].add(x);
		}
		Integer[] distances = new Integer[n];
		distances[0] = 0;
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		int ans = 0;
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			int dist = distances[cur] + 1;
			int dist2 = dist << 1;
			for (int next : nexts[cur]) {
				if (distances[next] == null) {
					distances[next] = dist;
					int pat = patience[next];
					int time = pat > dist2 ? dist2
							: (dist2 % pat) == 0 ? (dist2 / pat - 1) * pat + dist2 : dist2 / pat * pat + dist2;
					ans = Math.max(ans, time);
					queue.add(next);
				}
			}
		}
		return ans + 1;
	}

	private List<Integer>[] nexts(int[][] edges, int size) {
		List<Integer>[] nexts = new ArrayList[size];
		for (int i = 0; i < size; i++) {
			nexts[i] = new ArrayList<>();
		}
		for (int[] edge : edges) {
			int x = edge[0], y = edge[1];
			nexts[x].add(y);
			nexts[y].add(x);
		}
		return nexts;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(8, this.networkBecomesIdle(HelpDebug.str2array1("[[0,1],[1,2]]"), HelpDebug.str2array3("[0,2,1]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(3, this.networkBecomesIdle(HelpDebug.str2array1("[[0,1],[0,2],[1,2]]"), HelpDebug.str2array3("[0,10,10]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
